package a3;

import java.util.*;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleDirectedWeightedGraph;
import useful.*;

public class FordFulkerson implements FlowAlgorithm {
	protected int accessCount;
	
    @Override
    public double GetMaximalFlow(SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph, String q, String s) {
        accessCount = 0;
		double[][] flowMatrix = new double[graph.vertexSet().size()][graph.vertexSet().size()];
        Bijective<String, Integer> cityMap = new Bijective<>();
        int c = 0;
        for(String city : graph.vertexSet())
            cityMap.put(city, c++);
        
        
        
        List<String> vWeg = null;
        while ((vWeg = ChoosePath(graph,cityMap, flowMatrix, q, s)) != null) {
            double minDelta = Double.POSITIVE_INFINITY;
            for (int i = 0; i < vWeg.size() - 1; ++i) {
                String k1 = vWeg.get(i), k2 = vWeg.get(i+1);
                if (!graph.containsEdge(k1,k2)) //Rückwärtskante
                    minDelta = Math.min(minDelta, flowMatrix[cityMap.second(k2)][cityMap.second(k1)]);
                else //Vorwärtskante
                    minDelta = Math.min(minDelta, graph.getEdgeWeight(graph.getEdge(k1, k2)) - flowMatrix[cityMap.second(k1)][cityMap.second(k2)]);
            }
            for(int i = 0; i < vWeg.size() - 1; ++i) {
                String k1 = vWeg.get(i), k2 = vWeg.get(i+1);
                Integer i1 = cityMap.second(k1), i2 = cityMap.second(k2);
                if (!graph.containsEdge(k1,k2)) { //Rückwärtskante
                    flowMatrix[i2][i1] -= minDelta;
                } else { //Vorwärtskante
                    flowMatrix[i1][i2] += minDelta;
                }
            }
			System.out.println("  Delta: " + minDelta);
        }
        //Maximalen Fluß berechnen
        double flow = 0;
        for (DefaultWeightedEdge edge : graph.outgoingEdgesOf(q))
            flow += flowMatrix[cityMap.second(q)][cityMap.second(graph.getEdgeTarget(edge))];
        return flow;
    }
    
    @Override
    public int GetLastAccessCount() {
        return accessCount;
    }
    
    protected List<String> ChoosePath(SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph, Bijective<String,Integer> cityMap, double[][] currentFlowMatrix, String q, String s) {
		Random rand = new Random();
		Set<String> visited = new HashSet<>();
		List<Pair<String,List<String>>> vertexList = new ArrayList<>();
		List<String> result = new ArrayList<>();
		
		vertexList.add(new Pair(q, new ArrayList<>()));
		result.add(q);
		visited.add(q);
		
		while(!vertexList.isEmpty()) {
			int r = rand.nextInt(vertexList.size());
			Pair<String,List<String>> current = vertexList.remove(r);			
			
			List<String> way = current.second();
			String currentVertex = current.first();
			way.add(currentVertex);
			
			for(DefaultWeightedEdge edge : graph.outgoingEdgesOf(currentVertex)) {
				++accessCount;
				String targetVertex = graph.getEdgeTarget(edge);
				if (targetVertex.equals(s) && currentFlowMatrix[cityMap.second(currentVertex)][cityMap.second(s)] < graph.getEdgeWeight(edge)) {
					result = way;
					break;
				} else {
					if (!visited.contains(targetVertex) && currentFlowMatrix[cityMap.second(currentVertex)][cityMap.second(targetVertex)] < graph.getEdgeWeight(edge))  {
						vertexList.add(new Pair(targetVertex, new ArrayList<>(way)));						
						visited.add(targetVertex);
					}
				} 					
			}
			
			for(DefaultWeightedEdge edge : graph.incomingEdgesOf(currentVertex)) {
				++accessCount;
				String targetVertex = graph.getEdgeSource(edge);
				if (targetVertex.equals(s)) {
					result = way;
					break;
				} else {
					if (!visited.contains(targetVertex) && currentFlowMatrix[cityMap.second(targetVertex)][cityMap.second(currentVertex)] > 0)  {
						vertexList.add(new Pair(targetVertex, new ArrayList<>(way)));						
						visited.add(targetVertex);
					}
				} 					
			}
		
		}	
		if (result.size() > 1) {//Es gibt einen vergrößernden Weg
			result.add(s);
			System.out.print(result);
		} else 
			return null;
		return result;
    }
}
